import { quickSort } from './quick-sort';
import { findMinValue } from '../search/min-max-search';

/**
 * 桶排序：跟计数排序类似，只是我们准备的不是统计数组，而是桶这样的二维数组；遍历目标
 * 数组，将每个元素按照大小分配到对应的桶里（将元素分布到桶里）；所有元素遍历完后，桶
 * 之间是有顺序的但桶内部是没有顺序的，这里我们就需要对桶内部进行排序，一般选择快速排
 * 序或插入排序；每个桶都排完序后，将桶合并就会得到排好序的数组。到排好序的数组。
 * @param array 目标数组
 * @param bucketSize 桶大小（可以装多少元素）
 * 尽量将n个数据平均分配到k个桶中，这样每个桶就有n/k个数据量；尽量的增大桶的数量，极限
 * 情况下每个桶只能得到一个数据，这样就完全避开了桶内数据的排序操作。当然，做到这一点很
 * 不容易，数据量巨大的情况下，会使得桶的数量巨大，空间浪费严重。这就是一个时间代价和空
 * 间代价的权衡问题了。
 *
 * 对于n个待排数据，k个桶，平均每个桶n/k个数据这样情景的平均时间复杂度为：
 * O(n)+O(k\*(n/k)\*log(n/k))=O(n+nlog(n/k))。当k=n时，是最好效率的排序，也就是最好
 * 时间复杂度是O(n)。空间复杂度是O(n+k)
 */
export function bucketSort(array: number[], bucketSize: number = 5) {
    // 长度不足2无需排序
    if (array.length < 2) {
        return array;
    }

    // 构造桶数据
    const buckets: number[][] = createBuckets(array, bucketSize);

    // 将桶里的数据取出，这里利用插快速排序来对每个桶内进行排序
    const newArray = [];
    for (let i = 0, bl = buckets.length; i < bl; i ++) {
        // 快速排序对桶内的数据进行排序
        buckets[i] = quickSort(buckets[i]);
        // 将拍好序的桶数据加入到新数组里
        newArray.push(...buckets[i]);
    }
    return newArray;
}
/**
 * 生成桶数据
 * @param array 目标数组
 * @param bucketSize 桶的大小
 */
function createBuckets(array: number[], bucketSize: number): number[][] {
    // 这个数组里的最小值
    const minValue = findMinValue(array);

    // 构造桶这个二维数组
    const buckets: number[][] = new Array();

    // 遍历目标数组，将元素放入对应的桶中，桶满了就放入下一个桶中
    for (let i = 0, al = array.length; i < al; i ++) {
        // 目标数组遍历到的当前元素
        const current = array[i];
        // 当前元素会分布到哪个桶里（类似于计数排序）；分到桶后，桶之间是有大小顺序的。
        const bucketsIndex = Math.floor((current - minValue) / bucketSize);
        // 没初始化就要初始化
        if (buckets[bucketsIndex] == null) {
            buckets[bucketsIndex] = [];
        }
        buckets[bucketsIndex].push(current);
    }
    // 返回桶这个数据，桶之间排序了，但桶内部还没有排序
    return buckets;
}
